An integrated circuit (IC) has a large number of electronic components, such as transistors, logic gates, diodes, wires, etc., that are fabricated by forming layers of different materials and different geometric shapes on various regions of a wafer. The design of an integrated circuit transforms a circuit description into a geometric description called a layout. Layouts of complex chips have a very large number of individual shapes that are arranged in precise configurations to meet functional, electrical, performance and manufacturing specifications. The number of individual shapes has increased significantly as manufacturing concerns lead to the creation of new features like array instances for fill shapes.
Many phases of physical design may be performed with computer aided design (CAD) tools or electronic design automation (EDA) systems. To design an integrated circuit, a designer first creates high level behavior descriptions of the IC device using a high-level hardware design language. An EDA system typically receives the high level behavior descriptions of the IC device and translates this high-level design language into netlists of various levels of abstraction using a computer synthesis process. A netlist describes interconnections of nodes and components on the chip and includes information of circuit primitives such as transistors and diodes, their sizes and interconnections, for example. Geometric information about the placement of the nodes and components onto the chip is determined by a placement process and a routing process. The placement process is a process for placing electronic components or circuit blocks on the chip and the routing process is the process for creating interconnections between the blocks and components according to the specified netlist.
IC layouts are often constructed in a hierarchical fashion, in which a master design of a particular geometric element is created once, but where one or more instances (or occurrences) of the geometric element may be inserted into various locations and levels within the IC design. In this type of approach, the IC layout is hierarchically set out by re-using elements over and over again. Rather than copying duplicates of the same geometric element everywhere that it is used, instances of the elements are inserted in the appropriate locations that logically reference the appropriate master design. In the hierarchical approach, each instance provides a logical reference to its master design rather than a physical manifestation of the design at the instance locations. Some IC design systems distinguish between different types of hierarchical reuse, optimizing the representation for types of geometry that are heavily used, such as vias and contacts used to establish physical connections between different layers.
An advantage of this approach is improved efficiency with respect to memory usage when storing design data for an IC design. Memory efficiencies are gained since instances of an element are used and placed in the design, rather than requiring a full copy of that element to be duplicated numerous times in the design data.
However, the hierarchical nature of this approach can also cause inefficiencies when attempting to access the design data. As just one example, consider the process to search a portion of the IC design for the shapes within a particular search area. The search area may encompass parts of one or more instances in the design. However, only a subset of the shapes within the instances may actually fall within the search area. Because the shapes are not actually stored at each level, the search process may need to traverse the entire hierarchy of the corresponding instances on every layer and their nested instances to confirm which shapes in the instances overlap the search area, even through portions of the hierarchy that may not contain any shapes at the correct layer or design area. Depending upon the complexity of the design, this could be a very lengthy and expensive process.
In an alternate approach, the design hierarchy can be flattened so that the design data is not hierarchical in nature. In this approach, rather than inserting instances of elements into the design, actual copies of the elements are placed in the appropriate locations within the design data. The advantage of this approach is that it is very efficient to search the flattened design data, since chains of instances do not need to be followed to identify shapes within a search area. However, if the design includes a large number of geometric elements, then this approach may also consume an excessive amount of memory and storage resources. For at least this reason, it is often desirable to maintain the hierarchical nature of the electronic design (it is noted that there are also other reasons to preserve the hierarchy of the design, such as the desirability to reuse IP blocks and to minimize the complexity of changing a part of the design).
There are many types of EDA tools that need to be able to efficiently access hierarchical design data. For example, a layout editor is a tool that allows designers to view and modify components of the design at various levels of precision and control. Fundamentally, a layout editor operates to present some or all of a layout to a user, where the displayable portion of the layout is defined based upon some control or direction provided by the user which allows the tool to identify the specific objects on the specific layers and hierarchical levels that need to be displayed. Therefore, the layout editor must be able to efficiently query the layout database to find these objects in the hierarchical design data.
To accomplish this goal, design data should be organized in a scheme that is beneficial to the performance and memory footprint of such tools. The “Region Query” problem relates to the efficient organization of physical data for use in layout editors and other applications that depend upon repeated queries for objects contained in a specific region of the chip. Auxiliary structures are often maintained to facilitate the region query, where the auxiliary structures are distinct from the layout data that is physically stored for the design. The region query data structures can be thought of as an overlay that provides efficient access to subsets of the layout data, without changing the layout data itself.
A typical approach to implement auxiliary structures for the region query problem is to divide the chip into smaller partitions and to represent the components that overlap the partition as individual elements. The query problem reduces to an overlap detection problem—overlapping elements in partitions that overlap the query region are returned by the query. Elements that overlap multiple partitions are represented as duplicate references in all but one of those partitions, distinct from the original references on the partition for elements that are wholly contained in that partition. This approach breaks down with the introduction of fill (e.g., dummy or metal fill) for DFM (design for manufacturing) purposes. A particular technique to introduce fill is to create large array instances of fill shapes that are overlaid on top of the design. These instances appear as duplicates in every partition in the design, where such duplicates correspond to duplicated references in different partitions to the same underlying object in the layout that are large enough to intersect the area of each of those partitions. The proliferation of duplicates in this manner leads to an unacceptable increase in memory footprint, runtime and query time.
Conventional approaches to the Region Query problem use the divide and conquer principle, in which the entire chip is partitioned into smaller regions of variable or equal size. Each partition may be further decomposed into more partitions leading to a hierarchical decomposition of the space. The number of partitions at each level of the hierarchy may be fixed or may adapt to the size and organization of the data set. Objects that straddle multiple partitions may be represented as duplicates or may be represented only once in a higher level of the hierarchy. Design data is itself hierarchical, organized as instances of reusable child designs in parent designs. To avoid the need to descend through the entire hierarchy to query for objects on a specific layer, shadow views may be maintained to provide an aggregated view of all the objects below an instance of interest. The shadow view may be maintained on a per layer basis or based on a combination of a layer and a purpose. In addition, some types of geometric objects can be aggregated into a shadow view by type without regard to layer. Maintaining shadow views per layer for every design loaded in memory is expensive in terms of memory, initialization time and the effort required to maintain the integrity of the views during subsequent edits on the design hierarchy.
The conventional approaches to this problem all suffer from performance deficiencies. Several of these approaches will now be described with specific reference to their performance attributes based on factors such as memory footprint (VM), time required to initialize the Region Query auxiliary structures (initialization time), and queries of various sizes (full, large, medium, small).
The Binary or XY tree approach is based upon a variable sized, hierarchical, adaptive scheme that recursively splits the chip area, and maintains a single reference to each object while not maintaining shadow views. While the VM is small in this approach, the initialization time and query performance are quite poor.
The Quad Tree approach utilizes an equal sized, hierarchical, fixed structure that recursively splits the chip area into quadrants, maintains duplicate references to objects and does not maintain shadow views. One significant problem with this approach is that VM is large due to the duplicates maintained on all overlapping partitions at a level of hierarchy, even though the initialization time and query performance is better than the XY Tree.
The Zone Tree approach uses a variable sized, flat scheme that maintains duplicate references to objects and maintains shadow views. The VM is large due to the duplicates, and the initialization time is worse than Quad Tree, but the query performance is significantly better than either XY or Quad Trees due to the shadow views and the limited number of partitions that must be searched for overlapping objects of interest.
Therefore, there is a need for an improved approach to managing and querying layout data.